package Algorithm.interview;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author self
 * @Date 2024/10/14 19:32
 * @Describe 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，结果需要对 109 + 7 取模。
 * <p>
 * 示例 1：
 * <p>
 * 输入：s = "rabbbit", t = "rabbit"
 * 输出：3
 * 解释：
 * 如下所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
 * rabbbit
 * rabbbit
 * rabbbit
 * 示例 2：
 * <p>
 * 输入：s = "babgbag", t = "bag"
 * 输出：5
 * 解释：
 * 如下所示, 有 5 种可以从 s 中得到 "bag" 的方案。
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * babgbag
 * 提示：
 * <p>
 * 1 <= s.length, t.length <= 1000
 * s 和 t 由英文字母组成
 * ————————————————
 */

public class NumDistinct {

    /*   暴力算法：
        找到所有s的子序列，看有几个和t匹配（递归获取所有子序列）
        */
    public int getPatternSum(String s, String t) {
        if (s == null || s.length() == 0 || t == null || t.length() == 0) {
            return 0;
        }
        int res = 0;
        List<String> subString = findAllSubString(s);
        for (String str: subString) {
            if (str.equals(t)) {
                res++;
            }
        }
        return res;
    }

    private List<String> findAllSubString(String s) {
        List<String> subString = new ArrayList<>();
        // 递归调用
        recur("", s, subString);
        return subString;
    }

    private void recur(String current, String remain, List<String> subString) {
        // 终结条件
        if (remain.isEmpty()) {
            subString.add(current);
            return;
        }
        // 不取当前字符
        recur(current, remain.substring(1), subString);
        // 取当前字符
        recur(current + remain.charAt(0), remain.substring(1), subString);
    }

    public static void main(String[] args) {
        String s = "rabbbit";
        String t = "rabbit";
        NumDistinct numDistinct = new NumDistinct();
        int patternSum = numDistinct.getPatternSum(s, t);
        System.out.println(patternSum);
        int patternSum2 = numDistinct.getPatternSum("babgbag", "bag");
        System.out.println(patternSum2);
    }
}
